package it.uniroma3.dia.digraph.algorithm.utility;


import it.uniroma3.dia.digraph.algorithm.kouterplanar.kouterplanar.KouterplanarNode;
import it.uniroma3.dia.digraph.algorithm.stackedTri.GenerationBuilder;
import it.uniroma3.dia.digraph.algorithm.utility.kouterplanar.Peeler;
import it.uniroma3.dia.digraph.algorithm.utility.kouterplanar.outerplanar.OuterplanarNode;
import it.uniroma3.dia.digraph.algorithm.utility.polygon.GeneralPolygon;
import it.uniroma3.dia.digraph.algorithm.utility.stackedtri.StackedTriGraph;
import it.uniroma3.dia.digraph.algorithm.utility.stackedtri.StackedTriNode;

import java.awt.Point;
import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.graphdrawing.graphml.xmlns.EdgeType;
import org.graphdrawing.graphml.xmlns.GraphType;
import org.graphdrawing.graphml.xmlns.NodeType;

/**
 * A facade class to access any utility method offered by any class in this package.
 * @author Cionzo
 *
 */
public class Utility {

	
	/**
	 * Calculates the barycentric coordinates for point respect to the vertices of the triangle.
	 * @param point the point whose b.c. have to be calculated.
	 * @param v1 A vertex of the triangle
	 * @param v2 A vertex of the triangle
	 * @param v3 A vertex of the triangle
	 * @return an array with the b.c. 
	 */
	public static double[] barycentricCoords(NodeType point,
			NodeType v1, NodeType v2, NodeType v3) {
		return Triangle.barycentricCoords(point.getX(), point.getY(), v1.getX(), v1.getY(), v2.getX(), v2.getY(), v3.getX(), v3.getY());

	}

	/**
	 * Calculates the barycentric coordinates for point respect to the vertices of the triangle.
	 * @param point the point whose b.c. have to be calculated.
	 * @param v1 A vertex of the triangle
	 * @param v2 A vertex of the triangle
	 * @param v3 A vertex of the triangle
	 * @return an array with the b.c. 
	 */
	public static double[] barycentricCoords(Point2D.Double point,
			NodeType v1, NodeType v2, Point2D.Double v3) {
		return Triangle.barycentricCoords(point.getX(), point.getY(), v1.getX(), v1.getY(), v2.getX(), v2.getY(), v3.getX(), v3.getY());

	}


	/**
	 * Builds an adjacency matrix for the given graph
	 * @param graph the graph to be represented by the adjacency matrix  
	 * @return a map representing the adjacency matrix for the given graph
	 */
	public static Map<String, Set<String>> buildAdjacencyMatrix(GraphType  graph){
		return GeneralGraphStructure.buildAdjacencyMatrix(graph);
	}

	/**
	 * Checks whether the triangle abc contains any of the points in the list.
	 * @param a A vertex of the triangle
	 * @param b A vertex of the triangle
	 * @param c A vertex of the triangle
	 * @param nodes the nodes to check
	 * @return true if any node lies in the triangle, false otherwise.
	 */
	public static boolean containsAnyPoint(NodeType a, NodeType b,
			Point2D.Double c, Collection<NodeType> nodes){		
		return Triangle.contains(new Point2D.Double(a.getX(),a.getY()), new Point2D.Double(b.getX(), b.getY()), c, nodes);
	}

	/**
	 * Converts polar coords (with respect to the specified origin) to cartesian coords 
	 * @param origin the point considered as the origin
	 * @param alphaDegrees the angle, expressed in degrees
	 * @param radius the radius
	 * @return an array of two double values: [xCoord, yCoord]
	 */
	public static double[] convertToCartesianCoords(Point2D origin, double alphaDegrees, double radius) {
		return AngleManager.convertToCartesianCoords(origin, alphaDegrees, radius);
	}
	
	
	/**
	 * Groups graph nodes into layers. 
	 * Nodes on graph boundary are on layer 0, nodes on the boundary of g without layer 0 are on layer 1...
	 * @param graph the graph to decompose, it must be connected.
	 * @return a map i -> list_of_nodes_at_ith_layer
	 */
	public static Map<Integer, List<NodeType>> decomposeToLayers(GraphType graph) {
		return Peeler.decomposeToLayers(graph);
	}
	
	/**
	 * @param g
	 * @return
	 */
	public static Map<Integer, List<OuterplanarNode>> decomposeToOuterplanarLayers(
		GraphType g) {
	    Map<Integer, List<NodeType>> layers = decomposeToLayers(g);
	    Map<Integer, List<OuterplanarNode>> outLayers = new HashMap<Integer, List<OuterplanarNode>>(); 
	    List<OuterplanarNode> currentOutLayer;
	    List<NodeType> currentLayer;
	    for (Integer i : layers.keySet()) {
		currentOutLayer = new LinkedList<OuterplanarNode>();
		currentLayer = layers.get(i);
		
		for (NodeType n : currentLayer)
		    currentOutLayer.add(new OuterplanarNode(n));
		
		outLayers.put(i, currentOutLayer);
		
		
	    }
	    return outLayers;
	   
	}

	/**
	 * Calculates the determinant of a 2x2 matrix
	 * @param aij the values
	 * @return the determinant of a 2x2 matrix
	 */
	public static double det(double a11, double a12, 
			double a21, double a22){
		return det(new double[][]{{a11,a12},{a21,a22}});
	}

	/**
	 * Calculates the determinantof a 3x3 matrix
	 * @param aij the values
	 * @return the determinant of a 3x3 matrix
	 */
	public static double det(double a11, double a12, double a13, 
			double a21, double a22, double a23, 
			double a31, double a32, double a33){
		return Matrix.det(a11, a12, a13, a21, a22, a23, a31, a32, a33);
		
	}

	/**
	 * Calculates the determinantof a nxn matrix
	 * @param a the matrix
	 * @return the determinant of a nxn matrix
	 */
	public static double det(double[][] a){
		return Matrix.det(a);		
	}

	

	/**
	 * Calculates ab segment length.
	 * @param a an endpoint of the segment
	 * @param b an endpoint of the segment
	 * @return the length of the segment
	 */
	public static double distance(NodeType a, NodeType b){
		return Segment.length(a.getX(), a.getY(), b.getX(), b.getY());
	}
	
	/**
	 * Calculates ab segment length.
	 * @param a an endpoint of the segment
	 * @param b an endpoint of the segment
	 * @return the length of the segment
	 */
	public static double distance(NodeType a, Point2D b) {		
		return Segment.length(a.getX(), a.getY(), b.getX(), b.getY());
	}
	
	/**
	 * Calculates ab segment length.
	 * @param a an endpoint of the segment
	 * @param b an endpoint of the segment
	 * @return the length of the segment
	 */
	public static double distance(Point2D a, Point2D b){
		return a.distance(b);		
	}


	/**
	 * Checks whether segments ab and cd intersect.
	 * @param a segment ab source point
	 * @param b segment ab endpoint
	 * @param cx point c x coord
	 * @param cy point c y coord
	 * @param dx point d x coord
	 * @param dy point d y coord
	 * @return true if the segments intersect, false otherwise.
	 */
	public static boolean existsIntersection(NodeType a, NodeType b, double cx,
			double cy, double dx, double dy ) {
		Point pa = new Point();
		Point pb = new Point();
		Point pc = new Point();
		Point pd = new Point();

		pa.setLocation(a.getX(), a.getY());
		pb.setLocation(b.getX(), b.getY());
		pc.setLocation(cx, cy);
		pd.setLocation(dx, dy);
		return existsIntersection(pa, pb, pc, pd);
	}


	/**
	 * Checks whether edge AB intersects segment CD.
	 * @param a an endpoint of the edge
	 * @param b an endpoint of the edge
	 * @param c an endpoint of the segment
	 * @param d an endpoint of the segment
	 * @return true if the segments intersect, false otherwise
	 */
	public static boolean existsIntersection(NodeType a, NodeType b,
			Double c, Double d) {		
		return existsIntersection(a, b, c.getX(), c.getY(), d.getX(), d.getY());
	}

	
	/**
	 * Checks whether edge AB intersects segment CD.
	 * @param a an endpoint of the edge
	 * @param b an endpoint of the edge
	 * @param c an endpoint of the segment
	 * @param d an endpoint of the segment
	 * @return true if the segments intersect, false otherwise
	 */
	public static boolean existsIntersection(NodeType a, NodeType b, NodeType c, NodeType d){
		return existsIntersection(a, b, c.getX(), c.getY(), d.getX(),d.getY());
	}

	/**
	 * Checks whether edge AB intersects segment CD.
	 * @param a an endpoint of the edge
	 * @param b an endpoint of the edge
	 * @param c an endpoint of the segment
	 * @param d an endpoint of the segment
	 * @return true if the segments intersect, false otherwise
	 */
	public static boolean existsIntersection(NodeType a, NodeType b,
			NodeType c, Point d) {

		return existsIntersection(a, b, c.getX(), c.getY(), d.getX(), d.getY());
	}
	
	
	/**
	 * Checks whether edges AB and CD intersect.
	 * @param a an endpoint of the first edge
	 * @param b an endpoint of the first edge
	 * @param c an endpoint of the second edge
	 * @param d an endpoint of the second edge
	 * @return true if the segments intersect, false otherwise
	 */
	public static boolean existsIntersection(Point a, Point b, Point c, Point d){
		return Segment.existsIntersection(a, b, c, d);		  
	}

	/**
	 * Builds a Map "nodeId"->"node" for the nodes of the given graph
	 * @param graph the graph
	 * @return a Map "nodeId"->"node" for the nodes of the given graph
	 */
	public static Map<String, NodeType> extractNodes(GraphType graph) {
		Map<String, NodeType> result = new HashMap<String, NodeType>();
		for (NodeType n : graph.getNodeCollection().getNode())
			result.put(n.getId(), n);
		return result;
	}

	

	/**
	 * Calculates the vertices of the box whose base is the segment ab
	 * @param a a base vertex of the box
	 * @param b a base vertex of the box
	 * @param sideLength the length of the side of the box
	 * @param theta the angle formed by the sides
	 * @return the vertices of the box
	 */
	public static Double[] findBoxVertices(NodeType a, NodeType b,
			double height, double theta) {
		Point2D.Double aa = new Point2D.Double(a.getX(), a.getY());
		Point2D.Double bb = new Point2D.Double(b.getX(), b.getY());

		return findBoxVertices(aa, bb, height, theta);
	}

	/**
	 * Calculates the vertices of the box whose base is the segment ab
	 * @param a a base vertex of the box
	 * @param b a base vertex of the box
	 * @param sideLength the length of the side of the box
	 * @param theta the angle formed by the sides
	 * @return the vertices of the box
	 */
	public static Double[] findBoxVertices(Point2D.Double a, Point2D.Double b,
			double height, double theta) {

		return GeneralPolygon.findBoxVertices(a,b,height,theta);
	}

	/**
	 * Calculates the angle formed by a point p, referred to the origin o
	 * @param ox the x coord of the point to be considered as the origin
	 * @param oy the y coord of the point to be considered as the origin
	 * @param px p point x coord 
	 * @param py p point y coord
	 * @return the angle formed by a point p, referred to the origin o
	 */
	public static double getAngle(double ox, double oy, double px, double py) {
		return AngleManager.getAngle(ox, oy, px, py);

	}

	/**
	 * Calculates the angle formed by a point p, referred to the origin o
	 * @param o the point to be considered as the origin
	 * @param p the point p
	 * @return the angle described by a point p, referred to the origin o
	 */
	public static double getAngle(NodeType o, NodeType p){
		return AngleManager.getAngle(o, p);
	}
	
	/**
	 * Calculates the angle formed by a point p, referred to the origin o
	 * @param o the point to be considered as the origin
	 * @param px p point x coord 
	 * @param py p point y coord
	 * @return the angle formed by a point p, referred to the origin o
	 */
	public static double getAngle(Point2D origin, double px, double py) {
		return AngleManager.getAngle(origin.getX(), origin.getY(), px, py);
	}

	/**
	 * Calculates oab
	 * @param origin
	 * @param a
	 * @param b
	 * @return
	 */
	public static double getAngle(Point2D origin, NodeType a,
			NodeType b) {		
		return AngleManager.getUnsignedAngleDifference(origin, a, b);
	}

	public static double getAngle(Point2D.Double origin, NodeType node) {

		return getAngle(origin, node.getX(), node.getY());
	}

	public static double getAngle(Point2D.Double origin, Point2D.Double point) {

		return getAngle(origin, point.getX(), point.getY());
	}

	/**
	 * @return
	 */
	public static AngleManager getAngleComparator(){
		return new AngleManager();
	}

	/**
	 * Returns the circumcenter of the specified triangle
	 * @param a triangle vertex
	 * @param b triangle vertex
	 * @param c triangle vertex
	 * @return the circumcenter of the specified triangle
	 */
	public static Double getCircumCenter(NodeType a, Double b, NodeType c) {
		return Triangle.getCircumCenter(a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY());
	}


	/**
	 * Builds a map depthLevel-> nodes_at_depthLevel, for a stacked triangulation
	 * @param graph the stacked triangulation to decompose
	 * @return a map depthLevel-> nodes_at_depthLevel, for a stacked triangulation
	 */
	public static Map<Integer, List<StackedTriNode>> getDepthToNodes(
			GraphType graph) {
		return GenerationBuilder.getLayer2Nodes(graph);
	}

	/**
	 * Calculates the circumcenter of an isosceles triangle.
	 * @param baseMid the middle point of the base
	 * @param theta the angle formed by the tird
	 * @param baseVertex
	 * @param topVertex
	 * @return
	 */
	public static Point2D.Double getIsoscelesCircumCenter(Point2D.Double baseMid, double theta, NodeType baseVertex, Point2D.Double topVertex){
		return Triangle.getIsoscelesCircumCenter(baseMid, theta, baseVertex, topVertex);
	}

	public static List<NodeType> getNodesOnConvexHull(Collection<NodeType> nodes) {

		return GeneralGraphStructure.getNodesOnConvexHull(nodes);
	}

	public static List<StackedTriNode> getNodesOnConvexHull(
			List<StackedTriNode> outNodes) {
		Map<NodeType, StackedTriNode> map = new HashMap<NodeType, StackedTriNode>();
		for (StackedTriNode on : outNodes){
			map.put(on.getNode(), on);
		}
		List<StackedTriNode> result = new LinkedList<StackedTriNode>();
		for (NodeType n : getNodesOnConvexHull(map.keySet())){
			result.add(map.get(n));
		}
		return result;
	}

	/**
	 * Creates an outerplanar representation of a graph
	 * @param graph the graph to view as an outerplanar
	 * @return the "outerplanar version" of the input graph
	 */
	public static StackedTriGraph getOuterplanarGraph(GraphType graph) {

		return new StackedTriGraph(graph);
	}

	/**
	 * @param a the point that should be used as the origin
	 * @param b the point which will become an internal point 
	 * @param dist the distance that should be between point b and point result
	 * @return "a .... b .... result"
	 */
	public static Point getPointOnProlung(double sourceX, double sourceY, double targetX,
			double targetY, double distFromTarget) {
		return Segment.getPointOnProlung(sourceX, sourceY, targetX, targetY, distFromTarget);
	}

	/**
	 * @param a the point that should be used as the origin
	 * @param b the point which will become an internal point 
	 * @param dist the distance that should be between point b and point result
	 * @return "a .... b .... result"
	 */
	public static Point getPointOnProlung(NodeType a, NodeType b, double dist){

		return getPointOnProlung(a.getX(), a.getY(), b.getX(), b.getY(), dist);
	}

	/**
	 * @param a the point that should be used as the origin
	 * @param b the point which will become an internal point 
	 * @param dist the distance that should be between point b and point result
	 * @return "a .... b .... result"
	 */
	public static Point getPointOnProlung(Point a, Point b, double dist){
		return getPointOnProlung(a.getX(), a.getY(), b.getX(), b.getY(), dist);
	}

	/**
	 * Checks whether segment ab intersects segment cd
	 * @param a an endpoint of the first segment
	 * @param b an endpoint of the first segment
	 * @param c an endpoint of the second segment
	 * @param d an endpoint of the second segment
	 * @return true if the segment intersect, false otherwise 
	 */
	public static boolean intersection(NodeType a, NodeType b, NodeType c,
			NodeType d) {

		return Segment.intersection(a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY(), d.getX(), d.getY());
	}

	/**
	 * Checks whether segment ab intersects segment cd
	 * @param a an endpoint of the first segment
	 * @param b an endpoint of the first segment
	 * @param c an endpoint of the second segment
	 * @param triangleVertex an endpoint of the second segment
	 * @return true if the segment intersect, false otherwise 
	 */
	public static boolean intersection(NodeType a, NodeType b, NodeType c,
			Point2D triangleVertex) {

		return Segment.intersection(a.getX(), a.getY(), b.getX(), b.getY(), c.getX(), c.getY(), triangleVertex.getX(), triangleVertex.getY());
	}

	/**
	 * Checks whether the polygon described by the vertices is spannable.
	 * A polygon is spannable if both conditions are verified: 
	 * - its boundary does not intersect any of the edges in the list
	 * - it does not contain any of the nodes in the list.  
	 * @param boxVertices an ordered sequence of the vertices of the polygon
	 * @param edgeList a list with the edges to check for intersection
	 * @param nodesToCheck the nodes to be checked
	 * @param idToNodes a map id->node
	 * @return true if the polygon is spannable, false otherwise.
	 */
	public static boolean isSpannablePolygon(Double[] boxVertices, List<NodeType> nodesToCheck, List<EdgeType> edgeList, Map<String, NodeType> idToNodes) {
		return GeneralPolygon.isSpannablePolygon(boxVertices, nodesToCheck, edgeList, idToNodes);
	}
	
	/**
	 * Checks if the triangle "nodes[0]"-"current"-"point" is spannable by the nodes 1..current-1
	 * @param source a vertex of the triangle
	 * @param current a vertex of the triangle
	 * @param triangleVertex a vertex of the triangle
	 * @param edges the edges of the path
	 * @param nodes the nodes of the path
	 * @param id2nodes a map "nodeId"->"node"
	 * @return true if the triangle is spannable, false otherwise
	 */
	public static boolean isTspannable(NodeType source, NodeType current,
			Point2D triangleVertex, List<EdgeType> edges, List<NodeType> nodes, Map<String, NodeType> id2nodes) {

		return Triangle.isTspannable(nodes.get(0), current, triangleVertex, edges, nodes, id2nodes);
	}

	public static double length(double xa, double ya, double xb, double yb) {
		return Segment.length(xa, ya, xb, yb);

	}

	/**
	 * Calculates the length of the edge whose endpoints are a and b
	 * @param a
	 * @param b
	 * @return
	 */
	public static double length(NodeType a, NodeType b){
		return distance(a, b);
	}
	/**
	 * {@link length(NodeType a, NodeType b)}
	 */
	public static double length(Point2D a, Point2D b){
		return a.distance(b);		
	}

	public static void log(String methodName, NodeType current,
			NodeType previous, List<NodeType> nodes) {
		System.out.println(methodName+":");
		System.out.println("\tcurrent node: "+current);
		System.out.println("\tprevious node: "+previous);
		printNodeCollection(nodes);
		System.out.println();

	}

	public static Double midpoint(Double a, Double b) {

		return Segment.midPoint(a,b);
	}

	public static Point2D.Double midpoint(NodeType a, NodeType b) {
		return Segment.midPoint(a, b);
	}

	

	/**
     * Checks whether the specified node lies inside the polygon defined by points in boundary param.
     * It has been adapted from: <a href="http://www.cs.princeton.edu/introcs/35purple/Polygon.java.html">http://www.cs.princeton.edu/introcs/35purple/Polygon.java.html</a>
     * @param p the point to be checked
     * @param boundary the boundary of the polygon
     * @return true if the point lies inside the polygon, false otherwise.
     */
	public static boolean pointInPolygon(NodeType node, Point2D.Double boundary){
		return GeneralPolygon.contains(node, boundary);
	}


	public static void printNodeCollection(Collection<NodeType> nodes){
		for (NodeType node : nodes)
			System.out.print(node+" ");
	}

	public static void setDefalut(boolean value, NodeType... nodes) {
		for (NodeType n : nodes)
			n.setDefault(value);

	}

	/**
	 * @param on
	 * @param boundary
	 * @return
	 */
	public static Map<OuterplanarNode, java.lang.Double> homogeneusCoords(
		OuterplanarNode node, List<OuterplanarNode> nodes) {

	    return GeneralPolygon.homogeneusCoords(node, nodes);
	   
	}

	/**
	 * @param parents
	 */
	public static void sortByCCW(List<KouterplanarNode> parents) {
	    Peeler.sortByCCW(parents);
	}

	/**
	 * @param kouterplanarNode
	 * @param parents
	 * @return
	 */
	public static Map<KouterplanarNode, java.lang.Double> homogeneusCoords(
		KouterplanarNode kouterplanarNode,
		List<KouterplanarNode> parents) {
	   
//	    List<NodeType> pList = new LinkedList<NodeType>();
//	    for (KouterplanarNode n : parents)
//		pList.add(n.getNode());
//	    
	    return GeneralPolygon.homogeneusCoords(kouterplanarNode, parents);
	   
	}
	
	

	/**
	 * @param parentNodes
	 * @param adjacencyMatrix
	 * @return
	 */
	public static List<NodeType> getBoundary(
		List<NodeType> parentNodes,
		Map<String, Set<String>> adjacencyMatrix) {
	    Map<String, NodeType> nodeMap = new HashMap<String, NodeType>();
	    
	    for (NodeType node : parentNodes)
		nodeMap.put(node.getId(), node);
	    
	    return Peeler.getBoundaryNodes(parentNodes, adjacencyMatrix, nodeMap);
	}

	
















}
